<?php

/**
 * @copyright Michiel Hakvoort 2010
 * @license http://www.opensource.org/licenses/bsd-license.php New BSD
 * @package mangrove
 * @subpackage grove
 * @filesource
 */

/*
 * Copyright (c) 2010 Michiel Hakvoort
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

namespace mg;

/**
 * The Diff class provides a basic diff between two arrays. Given two input arrays and a optionally a comparator
 * Diff will create (and return) the diff array, indicating added, removed and unchanged entries between both arrays.
 *
 * Credits go to wikipedia contributors for providing excellent pseudocode.
 * http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
 *
 * @author Michiel Hakvoort <michiel@hakvoort.it>
 */
final class Diff {

    const ITEM_UNCHANGED = 0;
    const ITEM_ADDED = 1;
    const ITEM_REMOVED = 2;

    private function __construct() {

    }

    /**
     * Compute the basic diff
     *
     * @param array $first
     * @param array $second
     * @param Closure|null $comparator
     * @return array The computed diff array
     */
    public static function diff(array $first, array $second, Closure $closure = null) {

        reset($first);
        reset($second);

        $startOffset = 0;

        $isFinished = false;

        while(key($first) !== null && key($second) !== null && !$isFinished) {
            if(current($first) !== current($second)) {
                $isFinished = true;
            } else {
                $startOffset++;
                next($first);
                next($second);
            }
        }

        // prefix
        $prefix = array_slice($first, 0, $startOffset);

        $first = array_slice($first, $startOffset);
        $second = array_slice($second, $startOffset);

        end($first);
        end($second);

        $isFinished = false;

        $endOffset = 0;
        while(key($first) !== null && key($second) !== null && !$isFinished) {
            if(current($first) !== current($second)) {
                $isFinished = true;
            } else {
                $endOffset++;
                prev($first);
                prev($second);
            }
        }

        $postfix = array_slice($first, -$endOffset);

        $first = array_slice($first, 0, -$endOffset);
        $second = array_slice($second, 0, -$endOffset);

        $c = array();
        $m = count($first);
        $n = count($second);

        // cut off start

        // cut off end

        for($i = 0; $i <= $m; $i++) {
            $c[$i] = array_fill(0, $n+1, 0);
        }

        for($i = 1; $i <= $m; $i++) {
            for($j = 1; $j <= $n; $j++) {
                if($closure === null ? $first[$i-1] === $second[$j-1] : $closure($first[$i-1], $second[$j-1]) === 0) {
                    $c[$i][$j] = $c[$i-1][$j-1] + 1;
                } else {
                    $c[$i][$j] = max($c[$i][$j - 1], $c[$i-1][$j]);
                }
            }
        }

        $diff = self :: createDiff($c, $first, $second, $closure);

        end($prefix);
        while(key($prefix) !== null) {
            array_unshift($diff, array(self :: ITEM_UNCHANGED, current($prefix)));
            next($prefix);
        }

        foreach($postfix as $item) {
            array_push($diff, array(self :: ITEM_UNCHANGED, $item));
        }

        return $diff;
    }

    private static function createDiff($c, $m, $n, Closure $closure = null, $i = null, $j = null) {
        $i = $i === null ? count($m) : $i;
        $j = $j === null ? count($n) : $j;

        if($i > 0 && $j > 0 && ($closure === null ? $m[$i - 1] === $n[$j - 1] : $closure($m[$i-1], $n[$j - 1]) === 0)) {
            $diff = self :: createDiff($c, $m, $n, $closure, $i-1, $j-1);
            $diff[] = array(self :: ITEM_UNCHANGED, $m[$i-1]);
            return $diff;
        } else {
            if($j > 0 && ($i === 0 || $c[$i][$j-1] >= $c[$i-1][$j])) {
                $diff = self :: createDiff($c, $m, $n, $closure, $i, $j-1);
                $diff[] = array(self :: ITEM_ADDED, $n[$j-1]);
                return $diff;
            } elseif($i > 0 && ($j === 0 || $c[$i][$j-1] < $c[$i-1][$j])) {
                $diff = self :: createDiff($c, $m, $n, $closure, $i-1, $j);
                $diff[] = array(self :: ITEM_REMOVED, $m[$i-1]);
                return $diff;
            }
        }
        return array();
    }

}
